Development in a process technology makes it possible to mount a large number of Intellectual Properties (IPs) on a single chip, thereby satisfying multi-function and high-performance demand.
In such a chip, one IP needs to communicate with other many IPs and, therefore, a communication network is required. Under the circumstance, a method of connecting IPs to one another by means of point-to-point channels and routers in a structured manner is proposed, which is called Network on Chip (NoC).
FIG. 1 illustrates a general configuration of an information processing device using the NoC technology. As illustrated in FIG. 1, components each including an IP, a network interface, and a router are two-dimensionally arranged. In the left part of FIG. 1, two adjacent components are illustrated in an enlarged manner. An IP 101-1 is connected to a router 103-1 serving as a network node through a network interface 102-1 serving as an interface. An IP 101-2 is connected to a router 103-2 serving as a network node through a network interface 102-2 serving as an interface. The routers 103-1 and 103-2 are connected to each other by a point-to-point channel 104. Each of the IPs 101-1 and 101- is a hardware module such as a processor, a DSP (Digital Signal Processor), or a memory controller.
The IPs communicate with each other by exchanging data called a packet. Between the two adjacent IP 101-1 and IP 101-2, the IP 101-1 sends a packet to the router 103-1. The packet moves from the router 103-1 adjacent to the source IP to the router 103-2 adjacent to the destination IP 101-2, and finally reaches the destination IP 101-2. If the IP 101-1 and IP-101-2 are not adjacent to each other, the packet moves from the router 103-1 to the router 103-2 through one or more routers.
The routers illustrated in FIG. 1 each have a function of connecting a plurality of input channels and a plurality of output channels so as to transfer a packet. That is, each router outputs a packet coming from an input channel to an appropriate output channel so as to send the packet to the next router. The unit of data to be transferred between the routers is referred to as flit, and a packet is composed of one or more flits. Thus, actually, in the case where one packet is sent from one router to another, one or more header flits and zero or more subsequent flits are sent as the packet.
Processing performed by the router includes four tasks: Routing Calculation (RC) for determining the next router; Virtual Channel Allocation (VA) for assigning a virtual channel number to an input packet; Switch Allocation (SA) for arbitrating output channel requests issued to a crossbar in a router to which a packet is input and setting input/output connection relationship of the crossbar according to a result of the arbitration; and Switch Traversal (ST) for being moved the flit in the crossbar.
FIG. 2 is a block diagram of a typical router. The SA is also referred to input/output correspondence assignment processing. In FIG. 2, an IP section 212 corresponding to the IP of FIG. 1 is illustrated in addition to the router.
A related art concerning a system including a router for routing a packet and an IP will be described.
Referring to FIG. 2, a flit is input through an input channel 201 and buffered in an input port section 202. At this timing, a routing calculation section 206 determines which router is the next hop, that is, from which output channel the flit is to be output.
A virtual channel assignment section 207 determines a virtual channel number of a packet. A switch assignment section 209 performs arbitration between output channels for a plurality of packets in the input channel 201 or input port section 202 to determine an input/output relationship in a crossbar section 210. The flit passes through the crossbar section 210 and is then output to an appropriate output channel 211. A credit input 208 is input to the virtual channel assignment section 207, and a credit output 216 is output from the input port section 202.
NPL 1 discloses a technique that performs the above four tasks of the router in parallel or in a pipelined manner as much as possible so as to achieve a reduction of router's processing time and an increase of throughput. The operations of the four tasks depend on one another to some extent, so that processing cannot be completed in one stage. For example, the RC and SA depend on each other. Therefore, a pipeline stage includes, e.g., four stages. FIG. 3A illustrates a configuration example of the pipeline stage.
NPL 2 discloses a technique that reduces router's processing time by bringing the task of the router forward. That is, at the time point when a packet reaches a given router, the Routing Calculation (RC) for the next router is performed in advance. In this way, the task of the RC is brought forward. FIG. 3B illustrates a configuration view of a pipeline stage obtained as a result of application of this technique.
NPL 3 discloses a technique that reduces router's processing time by speculatively executing the VA and SA in parallel. FIG. 3C illustrates a configuration example of a pipeline stage obtained as a result of application of this technique.
Referring to FIG. 4, in a router according to related art (e.g., NPL 4), a prediction section 303 predicts an output channel 311 corresponding to an input channel 301 at which a flit is expected to arrive. After that, the flit enters from the input channel 301 to the router inputs. The packet passes through a crossbar section 301 and is output to the output channel 311. A credit input 308 is input to a virtual channel assignment section 307, and a credit output 316 is output from an input port section 302. A routing calculation section 306, a virtual channel assignment section 307, and a switch assignment section 309 have the same functions as those of the routing calculation section 206, a virtual channel assignment section 207, and a switch assignment section 209. An IP section 312 and a crossbar section 310 have the same functions as those of the IP section 212 and crossbar section 210.
The prediction is verified by the routing calculation section 306. If the prediction fails, the packet is invalidated before the packet reaches the next router. By performing input/output connection relationship setting processing of a crossbar switch in advance through the prediction, the operation of Switch Allocation (SA) is brought forward. FIG. 3(D illustrates a configuration example of a pipeline stage obtained as a result of application of this technique.
Referring to FIG. 5, a router according to related art (e.g., NPL 5) transmits a control packet to a destination router before transmitting a data packet. When the control packet is input to a router located on the traffic path, a routing calculation section 402 of the router determines an output channel. Further, an output schedule section 403 calculates the time at which both the output channel of the router and an input channel of the next router are unoccupied and records the calculation results in an output reservation table section 404. Subsequently, an input schedule section 405 records the arrival time of the data packet, the number of the input buffer in which the arrived data packet is stored, and time at which the data packet moves to an output channel 410, in an input reservation table section 406. Further, the time at which the data packet moves to the output channel 410, the number of the input buffer in which the data packet is stored, and an output channel number are recorded in an output reservation table section 404. A credit input 416 is input to the output reservation table section 404, and a credit output 417 is output from an input port section 408. A control packet output channel 418 is connected to the output schedule section 403.
In FIGS. 2, 4, and 5, the input port sections 202, 302, and 408 each have N input ports, while in an information processing device using the NoC technology illustrated in FIG. 1, each router has five input ports, that is, N is 5. In FIGS. 2 and 4, only one routing calculation section (206 or 306) is illustrated; actually, however, the routing calculation section is provided by the number of input ports.
As conventional art literatures relevant to the NoC, PLT 1, PLT 2, and PLT 3 exist.